package xio.leetcode.java;

/**
 * 208. Implement Trie (Prefix Tree) (Medium)
 * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 *
 * 示例:
 *
 * Trie trie = new Trie();
 *
 * trie.insert("apple");
 * trie.search("apple");   // 返回 true
 * trie.search("app");     // 返回 false
 * trie.startsWith("app"); // 返回 true
 * trie.insert("app");
 * trie.search("app");     // 返回 true
 * 说明:
 *
 * 你可以假设所有的输入都是由小写字母 a-z 构成的。
 * 保证所有输入均为非空字符串。
 *
 * 思路：因为输入是a-z 26个小写字母，所以我们可以设每个节点有26个子节点，以数组来存储字符。
 */
public class LC208_Trie {

    private Node root;
    private static final int MATCH_ALL = 0;
    private static final int MATCH_PRE = 1;

    /** Initialize your data structure here. */
    public LC208_Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            int index = index(word.charAt(i));
            if (cur.children[index] == null){
                cur.children[index] = new Node();
            }
            cur = cur.children[index];
        }
        cur.isLeaf = true;
    }


    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return match(word,MATCH_ALL);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return match(prefix,MATCH_PRE);
    }

    /**
     * 两种模式匹配字符串
     * @param str 待匹配的字符串
     * @param model 匹配模式，MATCH_ALL 是字符串完全匹配，MATCH_PRE 是前缀匹配
     * @return 先对待匹配字符串进行遍历，存在不匹配字符立刻返回False，全部可以匹配到则：
     * 在完全匹配模式下，需要前缀树也遍历到了叶节点才算完全匹配；
     * 在前缀匹配模式下，返回true即可。
     */
    private boolean match(String str, int model){
        Node cur = root;
        for (int i = 0; i < str.length(); i++) {
            int index = index(str.charAt(i));
            if (cur.children[index] == null){
                return false;
            }
            cur = cur.children[index];
        }
        return model == MATCH_PRE || cur.isLeaf;
    }

    private int index(char c){
        return c - 'a';
    }

    /** 节点 */
    private class Node {
        Node[] children = new Node[26];
        boolean isLeaf;
    }

    public static void main(String... args){
        LC208_Trie trie = new LC208_Trie();
        trie.insert("apple");
        System.out.println(trie.search("app"));
        System.out.println(trie.search("apple"));
        System.out.println(trie.startsWith("app"));
    }
}
